package 路径问题;

/**
 * @Date 2024/6/13 15:11
 * @description: 最小路径和
 * .            https://leetcode.cn/problems/minimum-path-sum/description/
 * @Author LittleNight
 */
public class likou64 {

    // 动态规划： 非常经典的一道题目
    // 两种处理边界值的方式
    public int minPathSum(int[][] grid) {
        // dp[i][j]状态表示: 从起点左上角到达（i，j） 位置的最小路径和

        // 1.创建 dp表
        // 2.初始化
        // 3.填表
        // 4.返回值
        // 动态规划 这里的是二维, 所以时空都是O(M*N)
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];

        // 初始化， 因为求得是最小值, 初始化的0有可能干扰结果
        // 新加的左边一列和上面一列都需要进行初始化为最大值
        for(int i = 0; i <= m; i++) dp[i][0] = Integer.MAX_VALUE; //新增行
        for(int j = 0; j <= n; j++) dp[0][j] = Integer.MAX_VALUE; //新增列
        dp[0][1] = dp[1][0] = 0; // 特殊处理边界

        // 做好映射关系, 原数组的(0,0) 对应dp表中的(1,1)
        // 这里填的是 dp 表, 所以建议从(1,1) 开始. 也就是dp表多加了一行一列
        for(int i = 1; i <= m; i++) { // 从上往下每一行
            for(int j = 1; j <= n; j++) { // 从左往右每一列
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
}
